/**
 * 
 */
package com.deep.test.algorithm;

/**
 * @author hudepin
 * 给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。
 * 比如字符串1：BDCABA；字符串2：ABCBDAB
        则这两个字符串的最长公共子序列长度为4，最长公共子序列是：BCBA
 *
 * 2018年5月9日下午2:27:18
 */
public class LCSDemo {
	
	public static int lcs(String s1,String s2){
		int[][] c= new int[s1.length()+1][s2.length()+1];
		for(int row=0;row<=s1.length();row++)
			c[row][0]=0;
		for(int column =0;column<=s2.length();column++)
			c[0][column]=0;
		for(int i=1;i<=s1.length();i++){
			for(int j=1;j<=s2.length();j++){
				System.out.println(i+"|"+j+",before c["+i+"]["+j+"]"+c[i][j]);
				if(s1.charAt(i-1)==s2.charAt(j-1)){
					c[i][j] = c[i-1][j-1]+1;
					System.out.println("i="+i+"j="+j+",char:"+s1.charAt(i-1));
				}
					
				else if(c[i][j-1]>c[i-1][j])
					c[i][j]=c[i][j-1];
				else
					c[i][j]=c[i-1][j];
				System.out.println(i+"|"+j+",after c["+i+"]["+j+"]"+c[i][j]);
				System.out.println("-------------------");
			}
		}
		return c[s1.length()][s2.length()];
	}
	public static void main(String[] args) {
		String s1="BC";
		String s2="ABCDC";
		System.out.println(lcs(s1, s2));
	}

}
